/*
 * randombiparti.cpp
 *
 *  Created on: 13 oct. 2011
 *      Author: gtempier
 */

#include <time.h>
#include <cstdlib>
#include "randombiparti.h"


int RandomBiparti::whatColorIs(int v, Graph graph, vector<int> colors) {
	int c = 0;
	int n = 0;
	for (int i=0; i < graph.numEdge(v); i++) {
		n = getVertexNeighbour(v,i); //voisin n°i de v
		if (colors[n] != 0)
			c = colors[n]%2+1;
		else
			c = whatColorIs(n, graph, colors);
		if (c != 0) {
			if (colors[v] == 0)
				colors[v] = c%2+1;
		}
	}
	return c;
}

RandomBiparti::RandomBiparti(int nbVertex, float proba) : Graph()
{
	generateRandomBiparti(nbVertex, proba);
}


void RandomBiparti::generateRandomBiparti(int vertex_num,float proba/*todo: *2 */) {
	srand(time(NULL));
	if (vertex_num < 1)
		return;

	vector<int> whites;
	vector<int> blacks; // cover vertices

	int nbBlacks = 1 + rand() % vertex_num; // on calcule un nombre aleatoire de sommets noirs
	int i;

	//on ajoute les sommets
	for (i = 0; i < nbBlacks; ++i) {
		blacks.push_back(addVertex());
	}
	for (i = 0; i < vertex_num - nbBlacks; ++i) {
		whites.push_back(addVertex());
	}

	//chaque sommet noir a une probabilite d'avoir une arete
	//avec un sommet blanc
	for (unsigned i = 0; i < blacks.size(); ++i) {
		for (unsigned j = 0; j < whites.size(); ++j) {
			if (rand() / (double)RAND_MAX < proba) {
				addEdge(blacks[i],whites[j]);
			}
		}
	}

#if 0
	cout << "White : ";
	for (unsigned i = 0; i < whites.size(); i++) {
		cout << whites[i] + 1 << " ";
	}
	cout << "\nBlack : ";
	for (unsigned i = 0; i < blacks.size(); i++) {
		cout << blacks[i] + 1<< " ";
	}
	cout << endl;
#endif
}
